package com.sicheng.algorithm.string;

import org.junit.Test;

@SuppressWarnings("all")
public class KMP {
    @Test
    public void kmp() {
        System.out.println(match("abbbacced", "abaab"));

    }

    //
    private void getNext(String model, Integer[] next) {
        next[0] = 0;    //当j = 0时，next[0] = 0
        int i = 1;
        int j = 0;
        int k = 0;
        while (i < model.length() && j < i) {

            if (model.substring(0, j).equals(model.substring(i - j, i))) {
                k = j;    //若有相同子串，则记录下对应在model模式串内的位置，最终得出最长匹配成功的位置
            }
            j++;

            if (j >= i) {
                next[i] = k;    //若一直未匹配成功，将k = 0赋值给next[i]
                j = 1;
                k = 0;
                i++;
            }
        }
    }

    //
    public int match(String main, String model) {
        int i = 0;
        int j = 0;
        Integer[] next = new Integer[model.length()];
        getNext(model, next);
        while (i < main.length() && j < model.length()) {
            if (main.charAt(i) == model.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
                if (main.charAt(i) != model.charAt(j))
                    i++;
            }
            if (j == model.length()) {
                return i - model.length();
            }
        }

        return -1;
    }


}
